package leetcodev1.字符串;

import leetcodev1.链表.Solution;

//有中间过程的话 可以考虑动态规划
public class LeetCode97 {

    //动态规划可以考虑使用滚动数组优化空间复杂度
    //双指针在相同元素下无法确定选择那个
    //动态规划 -> 逆向思维 适合判断是否有中间过程
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length(), length2 = s2.length(), length3 = s3.length();
        if (length1 + length2 != length3) {
            return false;
        }

        if (length1 == 0 && length2 == 0 && length3 == 0) {
            return true;
        }

        //dp[i][j]代表s3.substring(0,1)
        boolean[][] dp = new boolean[length1][length2];
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                char c = s3.charAt(i + j);
                if (i == 0 & j == 0) {
                    dp[0][0] = true;
                    continue;
                }

                if (i == 0) {
                    dp[0][j] = s3.substring(0, j).equals(s2.substring(0, j));
                    continue;
                }

                if (j == 0) {
                    dp[i][0] = s3.substring(0, i).equals(s1.substring(0, i));
                    continue;
                }

                dp[i][j] = (dp[i - 1][j] && s1.charAt(i) == c) || (dp[i][j - 1] && s2.charAt(j) == c);
            }
        }

        return dp[length1 - 1][length2 - 1];
    }
}

class Error97 {
    boolean ret = false;

    //正向思维
    //1.递归遍历所有结果 选a 选b
    //超出时间限制
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length(), length2 = s2.length(), length3 = s3.length();
        if (length1 == 0 && length2 == 0 && length3 == 0) {
            return true;
        }

        if (length1 + length2 != length3) {
            return false;
        }

        dfs(s1, s2, s3, 0, 0, length1, length2, length3);
        return ret;
    }

    private void dfs(String s1, String s2, String s3, int index1, int index2, int length1, int length2, int length3) {
        if (ret) {
            return;
        }

        int index = index1 + index2;
        if (index == length3) {
            ret = true;
            return;
        }

        if (index1 < length1 && s1.charAt(index1) == s3.charAt(index)) {
            dfs(s1, s2, s3, index1 + 1, index2, length1, length2, length3);
        }

        if (index2 < length2 && s2.charAt(index2) == s3.charAt(index)) {
            dfs(s1, s2, s3, index1, index2 + 1, length1, length2, length3);
        }
    }

}

class Answer97 {
    //如果子串已经不能满足则总的页不会满足
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        //字符串动态规划要+1 因为是开区间
        //i表示用s1个元素
        //j表示用s2个元素
        boolean[][] f = new boolean[n + 1][m + 1];

        f[0][0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;//总下标
                if (i > 0) {
                    //只用到了-1行，因此可以合并成一个数组
                    f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));//用s1
                    //这里没有有continue
                    //会继续向下执行
                }
                if (j > 0) {
                    f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));//用s2
                }
            }
        }

        //直接返回开区间
        return f[n][m];
    }

    //优化将dp打平
    public boolean isInterleave1(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();

        if (n + m != t) {
            return false;
        }

        boolean[] f = new boolean[m + 1];

        f[0] = true;
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                int p = i + j - 1;
                if (i > 0) {
                    f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);//不停的更新当前值
                }
                if (j > 0) {
                    f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));
                }
            }
        }

        return f[m];
    }
}
